// use random_number::{rand::random, random};

// 1. 堆-维护堆的性质-最大堆
pub fn max_heapify(a: &mut Vec<i32>, i: usize, len: usize) {
    let l: usize = (i << 1) + 1;
    let r: usize = (i + 1) << 1;
    let mut largest: usize = i;
    if l < len && a[l] > a[i] {
        largest = l;
    }
    if r < len && a[r] > a[largest] {
        largest = r;
    }
    if largest != i {
        a.swap(i, largest);
        println!("{} -> {}", i + 1, largest + 1);
        println!("{:?}", a);
        max_heapify(a, largest, len);
    } else {
        return;
    }
}
// 1-1. 维护堆的性质-最小堆
pub fn min_headify(a: &mut Vec<i32>, i: usize, len: usize) {
    let l: usize = (i << 1) + 1;
    let r: usize = (i + 1) << 1;
    let mut leastest = i;
    if l < len && a[l] < a[i] {
        leastest = l;
    }
    if r < len && a[r] < a[leastest] {
        leastest = r;
    }
    if leastest != i {
        a.swap(i, leastest);
        println!("{} -> {}", i + 1, leastest + 1);
        println!("{:?}", a);
        min_headify(a, leastest, len);
    } else {
        return;
    }
}

// 2. 建堆-最大堆
pub fn build_max_heap(a: &mut Vec<i32>) {
    let len = a.len();
    for i in (0..=(len >> 1)).rev() {
        max_heapify(a, i, len);
    }
}
// 2-1. 建堆-最小堆
pub fn build_min_heap(a: &mut Vec<i32>) {
    let len = a.len();
    for i in (0..=(len >> 1)).rev() {
        min_headify(a, i, len);
    }
}

// 3. 堆排序
pub fn heapsort(a: &mut Vec<i32>) {
    build_max_heap(a);
    let mut heap_size = a.len();
    for i in (1..a.len()).rev() {
        a.swap(0, i);
        heap_size -= 1;
        println!("--------------- >> {}", i);
        println!("{:?}", a);
        max_heapify(a, 0, heap_size)
    }
}

// 4. 优先队列
// 返回最大元素
pub fn heap_maximum(a: &Vec<i32>) -> i32 {
    a[0]
}
// 返回最大元素并删除
pub fn heap_extract_max(a: &mut Vec<i32>) -> Option<i32> {
    if a.len() < 1 {
        return None;
    }
    let max = a[0];
    a[0] = *(a.last().unwrap());
    a.remove(a.len() - 1);
    max_heapify(a, 0, a.len());
    Some(max)
}
// 将指定元素的值更新为新值，并维持优先队列的性质
pub fn heap_increase_key(a: &mut Vec<i32>, i: usize, key: i32) {
    if key < a[i] {
        panic!("new key is smaller than current key");
    }
    a[i] = key;
    let mut i = i;
    while i > 0 && a[i] > a[i >> 1] {
        a.swap(i, i >> 1);
        i >>= 1;
    }
}
// 插入新元素
pub fn max_heap_insert(a: &mut Vec<i32>, key: i32) {
    a.push(key);
    println!("{:?}", a);
    heap_increase_key(a, a.len() - 1, key);
}

// 5. 快速排序
// 分解
pub fn partition(a: &mut Vec<i32>, p: i32, r: i32) -> i32 {
    let x = a[r as usize];
    let mut i = p;
    for j in p..r {
        if a[j as usize] <= x {
            a.swap(i as usize, j as usize);
            println!("{} <----> {}", i + 1, j + 1);
            println!("{:?}", a);
            i += 1;
        }
    }
    a.swap(i as usize, r as usize);
    println!("{} <----> {}", i + 1, r + 1);
    println!("{:?}", a);
    println!("p -> {} ---- q -> {} ---- r -> {}", p + 1, i + 1, r + 1);
    return i;
}
// 快速排序
pub fn quicksort(a: &mut Vec<i32>, p: i32, r: i32) {
    if p < r {
        let q = partition(a, p, r);
        quicksort(a, p, q - 1);
        quicksort(a, q + 1, r);
    }
}
// 快速排序的随机化版本
// pub fn randomized_partition(a: &mut Vec<i32>, p: i32, r: i32) -> i32 {
//     let i = random!(p..=r);
//     println!("{:?}", a);
//     println!("SWAP {} ----> {}", i+1, r+1);
//     a.swap(i as usize, r as usize);
//     println!("{:?}", a);
//     return partition(a, p, r);
// }
// pub fn randomized_quicksort(a: &mut Vec<i32>, p: i32, r: i32) {
//     if p < r {
//         let q = randomized_partition(a, p, r);
//         randomized_quicksort(a, p, q-1);
//         randomized_quicksort(a, q+1, r);
//     }
// }
